package com.lenl.arithmetic.tenusablealgorithm.kmp;

import java.util.Arrays;

/**
 * @author Lenl
 * @version v1.0
 * @create 2022-05-14 14:51
 * @description KMP算法匹配字符串
 */
public class KMPAlgorithm {
    public static void main(String[] args) {
        String str1="BBC ABCDAB ABCDABCDABDE";
        String str2="ABCDABD";

        int[] next=kmpNext(str2);
        System.out.println(Arrays.toString(next));

        int index=kmpSearch(str1,str2,next);
        System.out.println("index="+index);

    }

    //写出kmp搜索算法

    /**
     *
     * @param str1 源字符串
     * @param str2 子串
     * @param next 子串的部分匹配表
     * @return
     */
    public static int kmpSearch(String str1,String str2,int[] next){
        //遍历
        for (int i=0,j=0;i<str1.length();i++){
            //处理str1.charAt(i)!=str2.charAt(j)
            //KMP算法核心
            while(j>0&&str1.charAt(i)!=str2.charAt(j)){
                j=next[j-1];
            }

            if(str1.charAt(i)==str2.charAt(j)){
                j++;
            }
            if(j==str2.length()){
                return i-j+1;
            }
        }
        return -1;
    }


    //获取到一个字符串（子串）的部分匹配值
    public static  int[] kmpNext(String dest){
        //初始化next数组
        int[] next=new int[dest.length()];
        next[0]=0;//如果字符串长度为1，则部分匹配值必为0
        for (int i=1,j=0;i<dest.length();i++){
            if(dest.charAt(i)==dest.charAt(j)){
                //部分匹配值+1
                j++;
            }else{
                //不等时，需要从next[j-1]获取新的j
                //直到发现有dest.charAt(i)==dest.charAt(j)时退出
                while(j>0&&dest.charAt(i)!=dest.charAt(j))
                    j=next[j-1];
            }
            next[i]=j;
        }
        return next;

    }

}
